{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "dda317e1",
   "metadata": {},
   "source": [
    "DP: Dynamic programming\n",
    " 子问题和原问题的关系（最优子结构）， 子问题和子问题的关系（重复子问题）；\n",
    " \n",
    "通常用于求解   最优化问题\n",
    "通过 划分并求解子问题来获得原问题的解。\n",
    "状态转移方程： f(n) 也叫状态 = f(n-1) + f(n-2)  描述了一种原问题与子问题的组合关系\n",
    "\n",
    "\n",
    "需要注意存在 重叠子问题， 且拥有最优子结构的情况。\n",
    "最优子结构是指： 每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到。\n",
    "也就是一个问题的最优解包含気子问题的最优解。\n",
    "\n",
    "4个步骤：\n",
    "1. 分析原问题最优解的结构特征；\n",
    "2. 递归的定义最优解的结构特征；\n",
    "3. 计算最优解的值，通常采用自底向上的方法；\n",
    "4. 综合计算信息，构造最优解。\n",
    "\n",
    "初始条件、边界等\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03ef52c9",
   "metadata": {},
   "source": [
    "# 旷工问题\n",
    "\n",
    "给定矿产和矿工数量的前提下，能够获得最多矿石的挖矿策略。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "995678f5",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "9bf59cfe",
   "metadata": {},
   "source": [
    "# 爬楼梯问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "068b40c4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "512\n"
     ]
    }
   ],
   "source": [
    "def goUpStairs(n):\n",
    "    if n < 1:\n",
    "        return (0)\n",
    "    \n",
    "    if n == 1:\n",
    "        return (1)\n",
    "    \n",
    "    if n == 2:\n",
    "        return (2)\n",
    "    \n",
    "    a = 1\n",
    "    b = 2\n",
    "    \n",
    "    for i in range(2, n):\n",
    "        sum = a + b\n",
    "        a = b \n",
    "        b = sum\n",
    "        \n",
    "    return  (sum)\n",
    "    \n",
    "    \n",
    "print(goUpStairs(10))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "trader",
   "language": "python",
   "name": "trader"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
